public class Solution264 {
    public int nthUglyNumber(int n) {
       /* LinkedList<Long> l1 = new LinkedList<>();
        LinkedList<Long> l2 = new LinkedList<>();
        LinkedList<Long> l3 = new LinkedList<>();
        HashSet<Long> set = new HashSet<>();
        long res = 1;
        for (int i = 1; i < n; i++) {
            if (set.add(res * 2)) {
                l1.add(res * 2);
            }
            if (set.add(res * 3)) {
                l2.add(res * 3);
            }
            if (set.add(res * 5)) {
                l3.add(res * 5);
            }
            long a = l1.getFirst(), b = l2.getFirst(), c = l3.getFirst();
            if (a < b && a < c) {
                res = l1.removeFirst();
            } else if (b < c) {
                res = l2.removeFirst();
            } else {
                res = l3.removeFirst();
            }
        }
        return (int) res;*/
        long[] dp = new long[n];
        dp[0] = 1;
        int p2, p3, p5;
        p2 = p3 = p5 = 0;
        for (int i = 1; i < n; i++) {
            long a = dp[p2] * 2, b = dp[p3] * 3, c = dp[p5] * 5;
            dp[i] = Math.min(a, Math.min(b, c));
            if (dp[i] == a) {
                p2++;
            }
            if (dp[i] == b) {
                p3++;
            }
            if (dp[i] == c) {
                p5++;
            }
        }
        return (int) dp[n - 1];
    }
}
